class Solution {
    class Graph{
    public:
        vector<int> child_vector;
        
        void add(int node)
        {
            child_vector.push_back(node);
        }
    };
    //从顶向下递归，从底向上汇总，最后形成了的顶部的节点的数量和总数都是正确的
    void deep_search(vector<Graph>& graph,vector<int>& result,vector<int>& count, int K,int Parent)
    {
        for(int i=0;i<graph[K].child_vector.size();++i)
        {
            int child=graph[K].child_vector[i];
            if(child!=Parent)
            {
                deep_search(graph,result,count,child,K);
                count[K]+=count[child];
                result[K]+=result[child]+count[child];
                
            }
        }
    }
    //计算出顶部的数量之后，在依靠临近节点的计数关系,从上向下依次得到正确的计数
    //sum_child_link=sum_child+sum_paret+count_parent;
    //sum_parent_link=sum_child+sum_paret+count_child;
    //count_parent+count_child=N;
    //sum_child_link=sum_parent_link+N-2*count_child;
    
    void deep_search2(vector<Graph>& graph,vector<int>& result,vector<int>& count, int K,int Parent)
    {
        for(int i=0;i<graph[K].child_vector.size();++i)
        {
            int child=graph[K].child_vector[i];
            if(child!=Parent)
            {   
                result[child]=result[K]+graph.size()-2*count[child];
                deep_search2(graph,result,count,child,K);
            }
        }
    }
public:
    vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) 
    { 
        vector<int> empty;
        
        if(N<=0||edges.size()!=N-1)
        {
            return empty;
        }
        if(N==1)
        {
            vector<int> one(1,0);
            return one;
        }
        vector<Graph> graph(N);
        for(int i=0;i<edges.size();++i)
        {
            if(edges[i].size()!=2||edges[i][0]==edges[i][1]
                ||edges[i][0]<0||edges[i][0]>=N
                ||edges[i][1]<0||edges[i][1]>=N)
            {
                return empty;
            }
            graph[edges[i][0]].add(edges[i][1]);
            graph[edges[i][1]].add(edges[i][0]);
        }
        vector<int> result(N,0);
        vector<int> count(N,1);
        deep_search(graph,result,count,0,-1);
        deep_search2(graph,result,count,0,-1);
       
        return result;
    }
};